package com.ryujung.hash.leetcode_49;
/*
 * @lc app=leetcode.cn id=49 lang=java
 *
 * [49] 字母异位词分组
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

// @lc code=start
class Solution {

    private static char[] chs;

    /**
     * 判断每一个字符串，将字母相同的词组放在同一个桶中，
     * 
     * q1：确保不同字母所在的桶不同：哈希算法设计
     */
    // 
    public static List<List<String>> groupAnagrams1(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chs = new char[26];
            for (char ch : str.toCharArray()) {
                chs[ch - 'a']++;
            }
            String s = String.valueOf(chs);
            if (!map.containsKey(s)) {
                map.put(s, new LinkedList<>());
            }
            map.get(s).add(str);
        }
        return new LinkedList<>(map.values());
    }

    // 排序
    public static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> result = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] chs = str.toCharArray();
            Arrays.sort(chs);
            String s = new String(chs);
            if (!result.containsKey(s))
                result.put(s, new LinkedList<>());
            result.get(s).add(str);
        }
        return new LinkedList<>(result.values());
    }

    public static void main(String[] args) {
        String[] strs = { "eat", "tea", "tan", "ate", "nat", "bat" };
        System.out.println(groupAnagrams(strs));
    }

}
// @lc code=end
